package LeetCode.month02.day53;

import java.util.HashMap;
import java.util.Map;

public class No106 {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        for (int i = 0; i < n; i++) {
            map.put(inorder[i],i);
        }
        return myBuildTree(inorder,postorder,0,n-1,0,n-1);
    }

    public TreeNode myBuildTree(int[] inorder,int[] postorder,int inorderLeft,int inorderRight,int postorderLeft,int postorderRight){
        if(inorderLeft>inorderRight) return null;
        TreeNode root = new TreeNode(postorder[postorderRight]);
        int rootIndex = map.get(root.val);
        root.left = myBuildTree(inorder,postorder,inorderLeft,rootIndex-1,postorderLeft,postorderLeft+rootIndex-1-inorderLeft);//左 根 右  左 右 根
        root.right = myBuildTree(inorder,postorder,rootIndex+1,inorderRight,rootIndex-inorderLeft+postorderLeft,postorderRight-1);
        return root;
    }
}
